package com.lun.swordtowardoffer2.c14;

public class MinFlipsMonoIncr {

	public int minFlipsMonoIncr(String str) {
		if(str == null || str.isEmpty()) {
			return 0;
		}
		
		int[][] dp = new int[2][2];//dp[0]为f，dp[1]为g
		
		char firstChar = str.charAt(0);
		
		dp[0][0] = firstChar == '0' ? 0 : 1;
		dp[1][0] = firstChar == '1' ? 0 : 1;
		
		int len = str.length();
		
		for(int i = 1; i < len; i++) {
			char ch = str.charAt(i);
			
			int fPrev = dp[0][(i - 1) & 1];
			int gPrev = dp[1][(i - 1) & 1];
			
			dp[0][i & 1] = ch == '0' ? fPrev : fPrev +  1;
			
			int tmpMin = Math.min(fPrev, gPrev);
			dp[1][i & 1] = ch == '1' ? tmpMin : tmpMin +  1;
		}
					
		return Math.min(dp[0][(len - 1) & 1], dp[1][(len - 1) & 1]);
	}
	
}
